#include <iostream>
#include <cstdlib>
#include <algorithm>

template <typename DT>
//创建双链表
class DoubleLinkedList
{
 private:
  //创建节点
  struct Node
  {
    //基本结构
    DT data;//数据
    Node* next;//指针，指向后一个节点
    Node* prev;//指针，指向前一个节点

    //构造函数
    Node( const DT & d = DT{}, Node* p = nullptr, Node *n = nullptr)
      : data{ d }, prev{ p }, next{ n } {}//构造含有基本结构的节点，数据为左值
    Node( DT && d, Node* p = nullptr, Node *n = nullptr)
      : data{ std::move(d) }, prev{ p }, next{ n } {}//构造含有基本结构的节点，数据为右值
  };
 public:
  //创建常量迭代器，储存指向当前节点的指针
  class const_iterator
  {
  public:
    //常量迭代器初始化
    const_iterator():current{nullptr}
    {}

    //重载*，调取当前位置节点的数据
    const DT& operator*() const
    {return retrieve();}

    //前置++，向后移动同时返回新地址
    const_iterator& operator++()
    {
      current = current->next;
      return *this;
    }

    //后置++，向后移动同时返回旧地址
    const_iterator operator++(int)
    {
      const_iterator old = *this;
      ++(*this);
      return old;
    }

    //前置--，向前移动同时返回新地址
    const_iterator& operator--()
    {
      current = current->prev;
      return *this;
    }

    //后置--，向前移动同时返回旧地址
    const_iterator operator--(int)
    {
      const_iterator old = *this;
      --(*this);
      return old;
    }

    //重载==，与常量迭代器rhs比较当前位置，相同为真
    bool operator == (const const_iterator& rhs) const
    {return current == rhs.current;}
    //重载!=，与常量迭代器rhs比较当前位置，不同为真
    bool operator != (const const_iterator& rhs) const
    {return !(*this == rhs);}

  protected:
    Node* current;//指针，指向当前节点

    //调取当前节点的数据
    DT& retrieve() const
    {return current->data;}

    //构造函数，构造current指针为p的常量迭代器
    const_iterator(Node* p)
      :current{p}{}

    friend class DoubleLinkedList<DT>;
  };

  //创建迭代器，继承常量迭代器
  class iterator:public const_iterator
  {
  public:
    //迭代器初始化
    iterator()
    {}

    //重载*，调取当前位置节点的数据
    DT& operator*()
    {return const_iterator::retrieve();}
    //重载*，调取当前位置节点的数据常量
    const DT&& operator*() const
    {return const_iterator::operator*();}

    //前置++，向后移动同时返回新地址
    iterator& operator++()
    {
      this->current = this->current->next;
      return *this;
    }

    //后置++，向后移动同时返回旧地址
    iterator operator++(int)
    {
      iterator old = *this;
      ++(*this);
      return old;
    }

    //前置--，向前移动同时返回新地址
    iterator& operator--()
    {
      this->current = this->current->prev;
      return *this;
    }

    //后置--，向前移动同时返回旧地址
    iterator operator--(int)
    {
      iterator old = *this;
      --(*this);
      return old;
    }
    
  protected:
    //构造函数，构造current指针为p的迭代器
    iterator(Node* p):const_iterator{p}
    {}

    friend class DoubleLinkedList<DT>;
  };
  
public:
  //创建空双链表
  DoubleLinkedList()
  {
    init();
  };

  //Big-Five
  //析构函数，释放内存空间
  ~DoubleLinkedList()
  {
    clear();
    delete head;
    delete tail;
  }
  //复制构造函数
  DoubleLinkedList(const DoubleLinkedList& rhs)
  {
    init();
    for(auto& x:rhs)
      push_back(x);
  };
  //复制赋值操作符，重载=
  DoubleLinkedList& operator = (const DoubleLinkedList& rhs)
  {
    DoubleLinkedList copy = rhs;
    std::swap(*this, copy);
    return *this;
  };
  //移动构造函数
  DoubleLinkedList(DoubleLinkedList&& rhs)
    :theSize{ rhs.theSize }, head{ rhs.head }, tail{ rhs.tail }
  {
    rhs.theSize = 0;
    rhs.head = nullptr;
    rhs.tail = nullptr;
  };
  //移动赋值操作符，重载=
  DoubleLinkedList& operator = (DoubleLinkedList&& rhs)
  {
    std::swap( theSize, rhs.theSize );
    std::swap( head, rhs.head );
    std::swap( tail, rhs.tail );
    return *this;
  };

  //调取头节点后一个位置
  iterator begin()
  {return {head->next};}
  //调取头节点后一个位置常量
  const_iterator begin() const
  {return {head->next};}
  //调取尾节点的位置
  iterator end()
  {return {tail};}
  //调取尾节点的位置常量
  const_iterator end() const
  {return {tail};}

  //统计链表大小
  int size() const
  {return theSize;}

  //判断链表是否为空
  bool empty() const
  {return size() == 0;}

  //清除链表
  void clear()
  {
    while(!empty())
      pop_front( );
  }

  //输出链表
  void printlist()
  {
    for (iterator itr = begin(); itr != end(); itr++)
      std :: cout << *itr << '\t';
    std :: cout << '\b' << std :: endl;
  }

  //获取链表最前节点的数据
  DT& front()
  {return *begin();}
  //获取链表最前节点的数据常量
  const DT& front() const
  {return *begin();}
  //获取链表最后节点的数据
  DT& back()
  {return *--end();}
  //获取链表最后节点的数据常量
  const DT& back() const
  {return *--end();}
  //在链表最前插入左值数据为x的节点
  void push_front(const DT& x)
  {insert(begin(), x);}
  //在链表最前插入右值数据为x的节点
  void push_front(DT&& x)
  {insert(begin(), std::move(x));}
  //在链表最后插入左值数据为x的节点
  void push_back(const DT& x)
  {insert(end(), x);}
  //在链表最后插入右值数据为x的节点
  void push_back(DT&& x)
  {insert(end(), std::move(x));}
  //删除链表最前的节点
  void pop_front()
  {erase(begin());}
  //删除链表最后的节点
  void pop_back()
  {erase(--end());}

  //在迭代器itr位置前插入左值数据为x的新节点
  iterator insert(iterator itr, const DT& x)
  {
    Node* p = itr.current;
    theSize++;
    return {p->prev = p->prev->next = new Node{ x, p->prev, p }};
  };
  //在迭代器itr位置前插入右值数据为x的新节点
  iterator insert(iterator itr, DT&& x)
  {
    Node* p = itr.current;
    theSize++;
    return {p->prev = p->prev->next = new Node{ std::move(x), p->prev, p }};
  };
  //删除迭代器itr位置的节点
  iterator erase(iterator itr)
  {
    Node *p = itr.current;
    iterator retVal{ p->next };
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    theSize--;
    return retVal;
  };
  //删除从from位置到to位置前的所有节点
  iterator erase(iterator from, iterator to)
  {
    for( iterator itr = from; itr != to; )
      itr = erase( itr );
    return to;
  };

private:
  int theSize;//双链表大小
  Node *head;//指针，指向头节点
  Node *tail;//指针，指向尾节点
  
  //双链表初始化
  void init()
  {
    theSize = 0;
    head = new Node;
    tail = new Node;
    head->next = tail;
    tail->prev = head;
  }
};
